Problem
Description
已知平面内 $N$ 个点的坐标，求欧氏距离下的第 $K$ 远点对。
Input
输入文件第一行为用空格隔开的两个整数$ N, K$。接下来$ N$ 行，每行两个整数 $X,Y$，表示一个点
的坐标。$1 \leq N \leq 100000， 1 \leq K \leq 100， K \leq \dfrac{N (N−1)}{2} ， 0 \leq X, Y < 2^31$。
Output
输出文件第一行为一个整数，表示第 $K $远点对的距离的平方（一定是个整数）。
Sample Input
10 5
0 0
0 1
1 0
1 1
2 0
2 1
1 2
0 2
3 0
3 1
Sample Output
9
Solution
这题是KDTree模板题啊Orzzz
然额本蒟蒻打了好久才调出来
原因：
简直了。。
附上蒟蒻代码：（太懒没时间打注释）
跑的实在是巨慢：
顺便说一句：那个MAX和MIN记录的是当前矩阵区域内最大的横纵坐标值1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
int N, K, nowD, root, ql, qr;
using namespace std;
struct node
{
long long dis;
inline bool operator < (const node &a) const
{
return a.dis < dis;
}
};
typedef struct KDTree
{
int d[2], Min[2], Max[2], l, r;
} KDT;
KDT Tree[MAXN];
priority_queue <node> Q;
inline long long sqr(long long a)
{
return a * a;
}
inline void MAX(KDT &a, KDT b, int type)
{
a.Max[type] = max(a.Max[type], b.Max[type]);
}
inline void MIN(KDT &a, KDT b, int type)
{
a.Min[type] = min(a.Min[type], b.Min[type]);
}
inline long long GetDis(int x, int y)
{
return sqr(Tree[x].d[0] - Tree[y].d[0]) + sqr(Tree[y].d[1] - Tree[x].d[1]);
}
inline bool cmp(KDT a, KDT b)
{
if (a.d[nowD] == b.d[nowD])
{
return a.d[nowD ^ 1] < b.d[nowD ^ 1];
}
else
return a.d[nowD] < b.d[nowD];
}
inline void Update(int x)
{
if (Tree[x].l) for (register int i = 0; i < 2; ++i) MAX(Tree[x], Tree[Tree[x].l], i), MIN(Tree[x], Tree[Tree[x].l], i);
if (Tree[x].r) for (register int i = 0; i < 2; ++i) MAX(Tree[x], Tree[Tree[x].r], i), MIN(Tree[x], Tree[Tree[x].r], i);
}
inline int Build(int l, int r, int D)
{
nowD = D;
int mid = (l + r) >> 1;
nth_element(Tree + l + 1, Tree + mid + 1, Tree + r + 1, cmp);
if (l < mid) Tree[mid].l = Build(l, mid - 1, D ^ 1);
if (mid < r) Tree[mid].r = Build(mid + 1, r, D ^ 1);
for (register int i = 0; i < 2; ++i)
Tree[mid].Min[i] = Tree[mid].Max[i] = Tree[mid].d[i];
Update(mid);
return mid;
}
inline long long Adis(KDT A, KDT B)
{
return max(sqr(A.d[0] - B.Min[0]), sqr(A.d[0] - B.Max[0])) + max(sqr(A.d[1] - B.Min[1]), sqr(A.d[1] - B.Max[1]));
}
inline void Query(int x)
{
long long dl = 0, dr = 0;
long long dis = GetDis(0, x);
if (dis > Q.top().dis)
{
Q.pop();
Q.push((node){ dis });
}
if (Tree[x].l) dl = Adis(Tree[0], Tree[Tree[x].l]);
if (Tree[x].r) dr = Adis(Tree[0], Tree[Tree[x].r]);
if (dl > dr)
{
if (dl > Q.top().dis) Query(Tree[x].l);
if (dr > Q.top().dis) Query(Tree[x].r);
}
else
{
if (dr > Q.top().dis) Query(Tree[x].r);
if (dl > Q.top().dis) Query(Tree[x].l);
}
}
int main(int argc, char **argv)
{
ios::sync_with_stdio(false);
cin >> N >> K;
for (register int i = 1; i <= N; ++i)
{
cin >> Tree[i].d[0] >> Tree[i].d[1];
}
root = Build(1, N, 0);
for (register int i = 1; i <= K * 2; ++i)
Q.push((node) { 0 });
for (register int i = 1; i <= N; ++i)
{
Tree[0].d[0] = Tree[i].d[0];
Tree[0].d[1] = Tree[i].d[1];
Query(root);
}
cout << Q.top().dis << endl;
return 0;
}